home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / othello.h < prev    next >
Encoding:
C/C++ Source or Header  |  1989-05-23  |  13.5 KB  |  359 lines
  1. /*-----------------------------------------------------------------------------
  2. OTHELLO.H
  3.  
  4. This file contains global function prototypes, external variable declarations,
  5. and manifest constant definitions for the othello program.
  6.  
  7. Revision History
  8. ----------------
  9. Jon Ward    17 Oct 1988    Initial Revision.
  10. Jon Ward    30 Oct 1988    Added typedef for move type.
  11. Jon Ward    01 Nov 1988    Added constant defs and macros.
  12. Jon Ward    04 Dec 1988    Changed fa_ndx_struct from a structure to an
  13.                            array.
  14. Jon Ward    12 Dec 1988    Started adding function prototypes and external
  15.                            declarations for global variables.
  16. Gary Culp   15 Dec 1988    Added declaration for delta_array, BELONGS macro.
  17. Gary Culp   19 Dec 1988    Updated prototypes for functions in PROTECT.C
  18. Gary Culp   22 Dec 1988    Added MAX_AFFECTED_PIECES.
  19. Gary Culp    2 Jan 1989    Added STATIC and BT_MAX_DEPTH
  20. Jon Ward     3 Jan 1989    Added prototypes for minimax functions.
  21.                 added prototype for limb removing DB function
  22. Jon Ward     7 Jan 1989    Added last_max_score extern for MINIMAX.C.
  23. -----------------------------------------------------------------------------*/
  24.  
  25.  
  26. /*-----------------------------------------------------------------------------
  27. For debugging purposes, it is sometimes useful to change 'static' functions and
  28. variables to global, so they will appear in MAP files.  This definition makes
  29. that easier to do.  Just define STATIC to be an empty string (For MSC, the
  30. command line option "/DSTATIC=" will do this.) Do not use STATIC to declare
  31. static variables inside functions!  They will turn into automatics, and cease
  32. to work correctly.
  33. -----------------------------------------------------------------------------*/
  34. #ifndef STATIC
  35. #define STATIC static
  36. #endif
  37.  
  38.  
  39. /*-----------------------------------------------------------------------------
  40. This constant represents the number of axes on the othello board that can 
  41. contain a capture. There are obviously 8 vertical and 8 horizontal columns and 
  42. rows. There are also 15 diagonal "rows" forward and 15 diagonal "rows" 
  43. backward. However, 4 of each of these 15 are eliminated because a row must 
  44. contain 3 or more cells for a capture to occur. The 2 diagonal "rows" nearest 
  45. each corner have only 1 and 2 cells.
  46. -----------------------------------------------------------------------------*/
  47.  
  48. #define NUM_CAPTURABLE_AXES (11 + 11 + 8 + 8)
  49.  
  50.  
  51. /*-----------------------------------------------------------------------------
  52. The following board structure will contain the definition for a particular
  53. board.
  54.  
  55. The board element will contain bits (as defined below) that tell whether a cell
  56. is empty or occupied and whether the piece in that cell is protected along an
  57. axis. Once a piece is protected along all 4 axes, it has become permanent and
  58. can never be changed in the remainder of this game.
  59.  
  60. The fa_bits (fa being full axis) is an array of bits that tell if a particular
  61. axis is completely full.  1 is added for the non-capturable axes and 7 is added
  62. to round up to the nearest byte.
  63. -----------------------------------------------------------------------------*/
  64.  
  65. #define FA_BITS_SIZE ((NUM_CAPTURABLE_AXES + 1 + 7) / 8)
  66.  
  67. struct board_struct
  68.   {
  69.   unsigned char board [10][10];
  70.   unsigned char fa_bits [FA_BITS_SIZE];
  71.   };
  72.  
  73. typedef struct board_struct board_type;
  74.  
  75.  
  76. /*-----------------------------------------------------------------------------
  77. Board manifest constants and macros for the board_struct board element.
  78.  
  79. Note that the first four bits (NO_PIECE thru OFF_BOARD) are mutually exclusive.
  80. Only one of them may be set at a given time.
  81.  
  82. This bit mapping is NOT arbitrary.  The IS_PERM macro is a good example of why
  83. it is not.  The program exploits the numerical properties of the variables
  84. built with these definitions, as well as extracting bits from them.
  85. -----------------------------------------------------------------------------*/
  86.  
  87. #define NO_PIECE    0x01    /* Empty cell, No disk there */
  88. #define US_PIECE    0x02    /* Cell occupied by our disk */
  89. #define THEM_PIECE    0x04    /* Cell occupied by their disk */
  90. #define OFF_BOARD    0x08    /* Cell is off the board */
  91. #define BD_AX        0x10    /* Backward diagonal axis protected */
  92. #define FD_AX        0x20    /* Forward diagonal axis protected */
  93. #define H_AX        0x40    /* Horizontal axis protected */
  94. #define V_AX        0x80    /* Vertical axis protected */
  95.  
  96. #define IS_PERM(cell) ((cell) > (NO_PIECE | BD_AX | FD_AX | H_AX | V_AX))
  97. #define BELONGS(cell,code) ((cell)&(code))
  98.  
  99. #define TEST_BITS(cell,bits) ((cell) & (bits))
  100. #define SET_BITS(cell,bits) ((cell) |= (bits))
  101. #define CLR_BITS(cell,bits) ((cell) &= ~(bits))
  102.  
  103.  
  104. /*-----------------------------------------------------------------------------
  105. Full axis table for FA index table and macros for setting and testing the FA
  106. bits.
  107. -----------------------------------------------------------------------------*/
  108.  
  109. typedef unsigned char fa_type [4];
  110.  
  111. #define BD_NDX 0    /* index for backward diagonal FA bit */
  112. #define FD_NDX 1    /* index for forward diagonal FA bit */ 
  113. #define H_NDX  2    /* index for horizontal FA bit */       
  114. #define V_NDX  3    /* index for vertical FA bit */         
  115.  
  116. #define WHICH_BYTE(ndx) ((unsigned char) (ndx) >> 3)
  117. #define BIT_N_BYTE(ndx) ((unsigned char) 1 << ((ndx) & 0x07))
  118.  
  119. #define SET_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] |= BIT_N_BYTE(bit))
  120. #define CHK_FA_BIT(fa,bit) ((fa) [WHICH_BYTE(bit)] & BIT_N_BYTE(bit))
  121.  
  122.  
  123. /*-----------------------------------------------------------------------------
  124. The following type is used to represent a number used for indexing into the
  125. database manager when referencing a node (limb) in one of the move trees.
  126. -----------------------------------------------------------------------------*/
  127.  
  128. typedef unsigned int key_type;
  129.  
  130. #define NO_KEY ((key_type) 0xFFFF)
  131.  
  132.  
  133. /*-----------------------------------------------------------------------------
  134. The following type is used to represent the row and column of an othello move.
  135.  
  136. Since there are only 8 rows and 8 columns on the othello board, the move can be
  137. reduced to 6 bits, 3 for the row and 3 for the column.  One of the remaining
  138. bits is used to indicate that the player (computer or opponent) has no valid
  139. moves.  The other bit will be used by the DBM to indicate that there is a board
  140. associated with a limb entry.
  141.  
  142. The GET_ROW/GET_COL macros extract and normalize the row and col stored in a
  143. move_type.
  144.  
  145. The SET_ROW/SET_COL macros initialize the row and col for a move_type.
  146.  
  147. The CLR_ROW/CLR_COL macros clear the row and col for a move_type.
  148. -----------------------------------------------------------------------------*/
  149.  
  150. typedef unsigned char move_type;
  151.  
  152. #define ROW_MASK    0x07    /* 3 bits for row number */
  153. #define COL_MASK    0x38    /* 3 bits for col number */
  154. #define NO_MOVE_MASK    0x40    /* bit set for no valid moves */
  155. #define BOARD_MASK    0x80    /* bit set in DBM if bottom level of tree */
  156. #define HASNT_MOVED BOARD_MASK /* returned by check_for_input() when
  157.                                   move has not been entered yet */
  158.  
  159. #define GET_ROW(move) ((move) & ROW_MASK) 
  160. #define GET_COL(move) (((move) & COL_MASK) >> 3)
  161.  
  162. #define SET_ROW(move,row) ((move) |= ((row) & 0x07))
  163. #define SET_COL(move,col) ((move) |= ((col) & 0x07) << 3)
  164.  
  165. #define CLR_ROW(move) ((move) &= ~ROW_MASK)
  166. #define CLR_COL(move) ((move) &= ~COL_MASK)
  167.  
  168. #define SET_ROW_COL(m,r,c) ((m) |= (((c) & 0x07) << 3) | ((r) & 0x07))
  169.  
  170.  
  171. /*-----------------------------------------------------------------------------
  172. The limb_type type represents the data that is contained at each branch (limb)
  173. in the move tree.
  174.  
  175. The bc union is either a key for the board at this limb, or is a key for the
  176. first child of this limb.  The move struct element will have the BOARD_MASK
  177. bit set if the bc element is a board key.  If the BOARD_MASK bit is NOT set,
  178. bc will be the child_key.
  179.  
  180. A value of NO_KEY indicates that there are no children or siblings.
  181. -----------------------------------------------------------------------------*/
  182.  
  183. struct limb_struct 
  184.   {
  185.   move_type move;        /* what we did to get here */
  186.   int score;            /* value of this limb */
  187.   key_type sibling_key;        /* key for next sibling of this limb */
  188.  
  189.   union
  190.     {
  191.     key_type child_key;        /* key for the limb's first child */
  192.     key_type board_key;        /* key for board at this limb */
  193.     } bc;
  194.  
  195.   };
  196.  
  197. typedef struct limb_struct limb_type;
  198.  
  199.  
  200. /*-----------------------------------------------------------------------------
  201. Maximum depth to build the tree
  202. -----------------------------------------------------------------------------*/
  203. #define BT_MAX_DEPTH 11
  204.  
  205.  
  206. /*-----------------------------------------------------------------------------
  207.                    BD_EVAL.C
  208. -----------------------------------------------------------------------------*/
  209. int bd_eval(
  210.    struct board_struct *board_ptr,
  211.    unsigned char which_color);
  212.  
  213. /*-----------------------------------------------------------------------------
  214.                     BDTTY.C
  215. -----------------------------------------------------------------------------*/
  216. void disp_board (board_type *board);
  217. void disp_row (int row);
  218. void disp_col (int col);
  219. void disp_clr_row_col (void);
  220. void disp_init (void);
  221. void disp_error_msg (char *msg);
  222. void disp_player_move (unsigned char player);
  223. void disp_player_cant_move (unsigned char player);
  224. void disp_player_moved_to (unsigned char player);
  225. void disp_pieces (int us, int them);
  226.  
  227. extern char us_char;
  228. extern char them_char;
  229.  
  230.  
  231. /*-----------------------------------------------------------------------------
  232.                    BUILDLVL.C
  233. -----------------------------------------------------------------------------*/
  234. int build_tree (
  235.    int depth_to_build,
  236.    unsigned char movers_color);
  237.  
  238. void update_tree_after_our_move (
  239.    key_type our_move);
  240.  
  241. /*-----------------------------------------------------------------------------
  242.                     FATABL.C
  243. -----------------------------------------------------------------------------*/
  244. extern fa_type fa_tabl [8][8];
  245.  
  246.  
  247. /*-----------------------------------------------------------------------------
  248.                     GETMOV.C
  249. -----------------------------------------------------------------------------*/
  250. move_type check_for_input (void);
  251. void init_input_vars (void);
  252.  
  253.  
  254. /*-----------------------------------------------------------------------------
  255.                    MINIMAX.C
  256. -----------------------------------------------------------------------------*/
  257. key_type find_best_move (
  258.    key_type root,
  259.    int depth);
  260.  
  261. key_type find_worst_move (
  262.    key_type root,
  263.    int depth);
  264.  
  265. extern int last_max_score;    /* score for last tree evaluated */
  266.  
  267.  
  268. /*-----------------------------------------------------------------------------
  269.                     MOVEIT.C
  270. -----------------------------------------------------------------------------*/
  271. int verify_move_and_update_board (
  272.   move_type move,
  273.   unsigned char player);
  274.  
  275. /*-----------------------------------------------------------------------------
  276.                    MOVE_GEN.C
  277. -----------------------------------------------------------------------------*/
  278. int find_move(
  279.    struct board_struct *board_ptr,
  280.    int start_displacement,
  281.    unsigned char movers_color,
  282.    int *affected_list);
  283.  
  284. /* affected_list needs room for this many entries */
  285. #define MAX_AFFECTED_PIECES 19
  286.  
  287.  
  288. /*-----------------------------------------------------------------------------
  289.                     OTHDBM.C
  290. -----------------------------------------------------------------------------*/
  291. void free_limb (key_type limb);
  292. void db_init (void);
  293. void db_kill (void);
  294.  
  295. key_type db_add_child (
  296.    key_type parent_key,
  297.    unsigned char move,
  298.    board_type *board,
  299.    int score);
  300.  
  301. int db_retrieve_board (
  302.    key_type key,
  303.    board_type *board);
  304.  
  305. limb_type far *db_retrieve_limb (
  306.    key_type key);
  307.  
  308. int db_delete_subtree (
  309.    key_type parent,
  310.    key_type child);
  311.  
  312. int db_almost_full (void);
  313. void init_borders (board_type *bd);
  314.  
  315. /*-----------------------------------------------------------------------------
  316.                    OTHELLO.C
  317. -----------------------------------------------------------------------------*/
  318. void main (void);
  319.  
  320. extern board_type curnt_bd;        /* board -- used for display */
  321. extern key_type curnt_top_limb;        /* key of limb for current board */
  322.  
  323.  
  324. /*-----------------------------------------------------------------------------
  325.                    PIECE_CT.C
  326. -----------------------------------------------------------------------------*/
  327. int piece_count(
  328.    struct board_struct *board_ptr,
  329.    unsigned char piece_type);
  330.  
  331. unsigned char who_can_move(struct board_struct *board_ptr);
  332.  
  333. /*-----------------------------------------------------------------------------
  334.                    PROTECT.C
  335. -----------------------------------------------------------------------------*/
  336. void update_protection_for_board(
  337.    struct board_struct *board_ptr,
  338.    int *affected_list, /* list of affected pieces, beginning with new piece */
  339.    int num_affected,   /* number of pieces in affected list */
  340.    unsigned char new_color);  /* new color for affected pieces */
  341.  
  342. void handle_changed_pieces(
  343.    struct board_struct *board_ptr,
  344.    int *affected_list,
  345.    int num_affected,
  346.    unsigned char new_color,
  347.    int prot_check_flag);
  348.  
  349. /*
  350.    For movement along an axis within a board, add or subtract
  351.    delta_array[axis_number] to a pointer to a cell within the board.
  352. */
  353. extern const int delta_array[4];
  354.  
  355.  
  356. /*-----------------------------------------------------------------------------
  357. -----------------------------------------------------------------------------*/
  358.  
  359.